import java.util.*;

/**
 * @author VernHe
 * @date 2021年09月14日 14:23
 */
public class Solution_0438 {
    /**
     * 第一次的方法
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new LinkedList<>();
        if (p.length() == 0 || p.length() > s.length()) {
            return result;
        }

        char[] sChars = s.toCharArray();
        int sLen = sChars.length;
        char[] pChars = p.toCharArray();
        int pLen = pChars.length;
        Arrays.sort(pChars);

        // 可以改进为使用数组来存储出现的次数，因为字母总共就26个
        Set<Character> pCharSet = new HashSet<>();
        for (char pChar : pChars) {
            pCharSet.add(pChar);
        }


        int[] flag = new int[sLen];
        for (int i = 0; i < sLen; i++) {
            // 有这个字符
            if (pCharSet.contains(sChars[i])) {
                if (i > 0) {
                    // 在前一个的基础上加一
                    flag[i] = flag[i-1] + 1;
                } else {
                    // 第一个
                    flag[i] = 1;
                }
            }
        }

        for (int i = 0; i < sLen; i++) {
            // 如果长度符合就一个一个去检查是否相等
            if (flag[i] >= pLen) {
                // 进行比较
                int startIndex = i - pLen + 1;
                char[] temp = new char[pLen];
                for (int j = 0; j < pLen; j++) {
                    temp[j] = sChars[startIndex + j];
                }
                Arrays.sort(temp);
                for (startIndex = 0; startIndex < pLen; startIndex++) {
                    if (temp[startIndex] != pChars[startIndex]) {
                        break;
                    }
                }
                if (startIndex == pLen) {
                    result.add(i - pLen +1);
                }
            }
        }

        return result;
    }

    /**
     * 第一次用数组代替Set的改进的方法
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> result = new LinkedList<>();
        if (p.length() == 0 || p.length() > s.length()) {
            return result;
        }

        char[] sChars = s.toCharArray();
        int sLen = sChars.length;
        char[] pChars = p.toCharArray();
        int pLen = pChars.length;

        // 可以改进为使用数组来存储出现的次数，因为字母总共就26个
        int[] sCnt;
        int[] pCnt = new int[26];

        for (int i = 0; i < pLen; i++) {
            pCnt[pChars[i] - 'a']++;
        }

        int[] flag = new int[sLen];
        for (int i = 0; i < sLen; i++) {
            // 有这个字符
            if (pCnt[sChars[i] - 'a'] != 0) {
                if (i > 0) {
                    // 在前一个的基础上加一
                    flag[i] = flag[i-1] + 1;
                } else {
                    // 第一个
                    flag[i] = 1;
                }
            }
            // 判断是否匹配
            if (flag[i] >= pLen) {
                sCnt = new int[26];
                int j = 0;
                for (; j < pLen; j++) {
                    sCnt[sChars[i - j] - 'a']++;
                }
                if (j == pLen) {
                    if (Arrays.equals(sCnt, pCnt)) {
                        result.add(i - pLen + 1);
                    }
                }
            }
        }

        return result;
    }

    /**
     * 第二次改进方法，滑动窗口比较
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> result = new LinkedList<>();
        if (p.length() == 0 || p.length() > s.length()) {
            return result;
        }

        char[] sChars = s.toCharArray();
        int sLen = sChars.length;
        char[] pChars = p.toCharArray();
        int pLen = pChars.length;

        // 可以改进为使用数组来存储出现的次数，因为字母总共就26个
        int[] sCnt = new int[26];
        int[] pCnt = new int[26];

        // 初始化，使得sCnt中只存储着和pCnt一样多的字符
        for (int i = 0; i < pLen; i++) {
            sCnt[sChars[i] - 'a']++;
            pCnt[pChars[i] - 'a']++;
        }

        if (Arrays.equals(sCnt,pCnt)) {
            result.add(0);
        }

        // 滑动窗口，从左往右滑动，不断更新sCnt中字母的出现次数
        for (int i = pLen; i < sLen; i++) {
            // 窗口最左的字符出去
            sCnt[sChars[i - pLen] - 'a']--;
            // 窗口最右的字符进来
            sCnt[sChars[i] - 'a']++;
            if (Arrays.equals(sCnt, pCnt)) {
                result.add(i - pLen + 1);
            }
        }

        return result;
    }

    public static void main(String[] args) {
//        List<Integer> list = new Solution_0438().findAnagrams("cbaebabacd","abc");
        List<Integer> list = new Solution_0438().findAnagrams2("abab","ab");
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }
}
